package leetcode.动态规划.middle;

import java.util.Arrays;

/**
 * @author wangmaolin1
 * @date 2024/3/12 22:33
 */
public class _322 {
    int[]back;
    public int coinChange(int[] coins, int amount){
        back=new int[amount+1];
        Arrays.fill(back,-1111);
        return coinc(coins,amount);

    }

    private int coinc(int[] coins, int amount) {
        if (amount==0){
            return 0;
        }
        if (amount<0){
            return  -1;
        }
        if (back[amount]!=-1111){
            return back[amount];
        }
        int val = Integer.MAX_VALUE;
        for (int k = 0; k <coins.length; k++) {
           int res= coinc(coins,amount-coins[k]);
           if (res>-1){
               val = Math.min(res+1,val);
           }
        }
        back[amount]=val==Integer.MAX_VALUE?-1:val;
        return back[amount];
    }
}
